# 在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
# 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
# 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
# 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

def heapSort(todoList):
    length = len(todoList)
    if length < 2:
        return todoList
    while True:
        for i in range(int(length / 2) + 1, -1, -1):
            left = 2 * i + 1
            right = 2 * i + 2
            if left < length and todoList[i] < todoList[left]:
                todoList[i], todoList[left] = todoList[left], todoList[i]
            if right < length and todoList[i] < todoList[right]:
                todoList[i], todoList[right] = todoList[right], todoList[i]
        todoList[0], todoList[length - 1] = todoList[length - 1], todoList[0]

        if length == 1:
            break
        length -= 1
    return todoList
